package leecoke;

import java.util.Stack;

public class Test445 {
    public static class ListNode{
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = listLen(l1);
        int len2 = listLen(l2);
        // 长链表
        ListNode node1 = len1 > len2 ? l1 : l2;
        // 短链表
        ListNode node2 = node1 == l1 ? l2 : l1;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while(node1 != null){
            stack1.push(node1);
            node1 = node1.next;
        }
        while(node2 != null){
            stack2.push(node2);
            node2 = node2.next;
        }
        // 短链表不为空则两个链表相加
        int carry = 0;
        int sum = 0;
        ListNode res = null;
        ListNode newNode = null;
        while(!stack2.isEmpty()){
            // 记得需要加进位数字
            sum = stack1.pop().val + stack2.pop().val + carry;
            // 是否需要进位
            carry = sum >= 10 ? 1 : 0;
            // 如果需要进位则 sum 只取余数
            sum = sum % 10;
            newNode = new ListNode(sum);
            if(res == null){
                res = newNode;
            } else {
                newNode.next = res;
                res = newNode;
            }
        }
        // 处理长链表
        while(!stack1.isEmpty()){
            sum = stack1.pop().val + carry;
            // 是否需要进位
            carry = sum >= 10 ? 1 : 0;
            // 如果需要进位则 sum 只取余数
            sum = sum % 10;
            newNode = new ListNode(sum);
            if(res == null){
                res = newNode;
            } else {
                newNode.next = res;
                res = newNode;
            }
        }
        if(carry != 0){
            newNode = new ListNode(1);
            newNode.next = res;
            res = newNode;
        }
        return res;
    }

    public void addFirst(ListNode head, ListNode newHead){
        ListNode node = head;
        newHead.next = node;
    }


    public static int listLen(ListNode head){
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }
        return len;
    }
}
